/// @tags: DPwithNumber
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 55;

int K;
int a[N];
LL f[N][10000];
LL L, R;

LL dfs(int x, int sum, int tar, bool lim) {
  if (sum < 0) return 0;
  if (!x) return max(sum, 0);
  if (!lim && ~f[x][sum]) return f[x][sum];
  int num = lim ? a[x] : K - 1;
  LL ans = 0;
  for (int i = 0; i <= num; ++i)
    ans += dfs(x - 1, sum + (tar == 1 ? i * (x - 1) : (x < tar ? -i : i)), tar,
               lim && (i == num));
  if (!lim) f[x][sum] = ans;
  return ans;
}

inline LL solve(LL x) {
  int n = 0;
  while (x) a[++n] = x % K, x /= K;
  LL ans = 0;
  for (int i = 1; i <= n; ++i) {
    memset(f, -1, sizeof(f));
    ans += (i == 1 ? 1 : -1) * dfs(n, 0, i, 1);
  }
  return ans;
}

inline int main() {
  cin >> L >> R >> K;
  cout << solve(R) - solve(L - 1);
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3286 [SCOI2014] 方伯伯的商场之旅.in", "r", stdin);
  freopen("P3286 [SCOI2014] 方伯伯的商场之旅.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
